Definition(s)

Description of the algorithm for next_permutation:

Find largest index i such that array[i − 1] < array[i]. (If no such i exists, then this is already the last permutation.)

Find largest index j such that j ≥ i and array[j] > array[i − 1].

Swap array[j] and array[i − 1].

Reverse the suffix starting at array[i].

Algortihm(s)



In [1]:

    
def next_permutation(perm):
    n = len(perm)

    # Find longest non-increasing suffix
    i = n - 1
    while i > 0 and perm[i - 1] >= perm[i]:
        i -= 1

    # Is this the last permutation?
    if i <= 0:
        return False

    # perm[i - 1] is the pivot
    # search for the rightmost j such that perm[j] > perm[i - 1]
    j = n - 1
    while perm[j] <= perm[i - 1]:
        j -= 1

    assert j >= i

    # perm[j] will become the new pivot (swap perm[i-1] and perm[j])
    perm[i - 1], perm[j] = perm[j], perm[i - 1]

    # reverse the suffix perm[i..j]
    perm[i:j+1] = perm[i:j+1][::-1]

    return True

# generator for all permutations
def permutations(perm):
    is_next = True

    while is_next:
        yield perm
        is_next = next_permutation(perm)

Run(s)



In [3]:

    
p = [1, 3, 2, 4]
print(next_permutation(p), p)









    



True [1, 3, 4, 2]



In [4]:

    
p = [2, 4, 3, 7, 6, 8, 9, 5, 1, 0]
print(next_permutation(p), p)









    



True [2, 4, 3, 7, 6, 9, 8, 5, 1, 0]



In [5]:

    
for p in permutations(list(range(4))):
    print(p)









    



[0, 1, 2, 3]
[0, 1, 3, 2]
[0, 2, 1, 3]
[0, 2, 3, 1]
[0, 3, 2, 1]
[1, 0, 2, 3]
[1, 0, 3, 2]
[1, 2, 0, 3]
[1, 2, 3, 0]
[1, 3, 2, 0]
[2, 1, 3, 0]
[2, 3, 1, 0]
[3, 2, 1, 0]



In [6]:

    
p = ['a', 'l', 'e', 'x']
print(next_permutation(p), p)









    



True ['a', 'l', 'x', 'e']